package com.fmm.medium;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BinaryTreeRightView {
    public record TreeNode(int val, TreeNode left, TreeNode right) {
    }

    /**
     * @param root 二叉树根节点
     * @return 二叉树右视图能看到的节点列表
     */
    public static List<Integer> rightSideView(TreeNode root) {
        // 使用深度优先遍历，先遍历右节点
        // 记录每一层最右边的节点，key：层(从 0 开始)，value：最右边节点值
        Map<Integer, Integer> levelValueMap = new HashMap<>();
        rightSideView(root, levelValueMap, 0);
        return levelValueMap.values().stream().toList();
    }

    /**
     * 递归实现
     *
     * @param root         当前节点
     * @param levelValueMap 层值映射
     * @param level        当前节点位于哪层
     */
    private static void rightSideView(
            TreeNode root, Map<Integer, Integer> levelValueMap, int level) {
        // 当前节点为 null，无需处理，当前节点不为 null，判断当前层是否已经有最右值，有的话不处理，没有的话，把自己加入映射
        if (root == null) {
            return;
        }
        TreeNode right = root.right();
        TreeNode left = root.left();
        Integer value = levelValueMap.get(level);

        if (value == null) {
            levelValueMap.put(level, root.val());
        }
        // 把自己加入映射后，递归处理右左节点（右节点优先）
        rightSideView(right, levelValueMap, level + 1);
        rightSideView(left, levelValueMap, level + 1);
    }
}
